import functools


class Solution(object):
    def pathsWithMaxScore(self, board):
        m = len(board)
        n = len(board[0])
        base = 10 ** 9 + 7
        @functools.cache
        def dfs(x, y):
            if x == 0:
                if y == 0:
                    return [0, 1]
                else:
                    last_val, last_count = dfs(x, y - 1)
                    if last_count != 0 and board[x][y] != 'X':
                        return [last_val + int(board[x][y]), last_count % base]
                    else:
                        return [0, 0]
            else:
                if y == 0:
                    last_val, last_count = dfs(x - 1, y)
                    if last_count != 0 and board[x][y] != 'X':
                        return [last_val + int(board[x][y]), last_count % base]
                    else:
                        return [0, 0]
                else:
                    max_val = 0
                    max_count = 0
                    if board[x][y] == 'X':
                        return [0, 0]
                    else:
                        last_val, last_count = dfs(x - 1, y)
                        if last_count != 0:
                            if last_val > max_val:
                                max_val = last_val
                                max_count = last_count
                            else:
                                if last_val == max_val:
                                    max_count += last_count
                        last_val, last_count = dfs(x, y - 1)
                        if last_count != 0:
                            if last_val > max_val:
                                max_val = last_val
                                max_count = last_count
                            else:
                                if last_val == max_val:
                                    max_count += last_count
                        last_val, last_count = dfs(x - 1, y - 1)
                        if last_count != 0:
                            if last_val > max_val:
                                max_val = last_val
                                max_count = last_count
                            else:
                                if last_val == max_val:
                                    max_count += last_count
                        if x == m - 1 and y == n - 1:
                            return [max_val, max_count % base]
                        else:
                            return [max_val + int(board[x][y]), max_count % base]

        return dfs(m - 1, n - 1)



data = Solution()
board = ["E23", "2X2", "12S"]
print(data.pathsWithMaxScore(board))
